//组合 力扣77
//回溯算法
//改进：进行了剪枝，将最后剩余元素个数不足以满足要求的情况进行剪枝
class Solution {
public:
	
	void _combine(int n,int k,int startindex,vector<int>& path,vector<vector<int>>& ans)
	{
		if(path.size() == k)
		{
			ans.push_back(path);
			return;
		}
		for(int i = startindex; i <= n-(k-path.size())+1; i++)
		{
			path.push_back(i);
			_combine(n,k,i+1,path,ans);
			path.pop_back();
			
		}
		
		
	}
	vector<vector<int>> combine(int n, int k) {
		vector<int> path;
		vector<vector<int>> ans;
		_combine(n,k,1,path,ans);
		return ans;
	}
};
